Problems of fair arbitration are common in modern electronic devices and systems. These problems arise when there is competition among multiple inputs for access to some limited processing resource. Frequently, the inputs have different priority levels, as well as different weights, corresponding to the relative shares of the resource that they are entitled to receive. The priorities and weights may typically change dynamically in the course of operation of the circuit. Under these circumstances, it is necessary to implement a design that will ensure that the inputs are serviced in order of priority, and that each input receives its fair share of the resource in proportion to its assigned weight.
For example, arbitration schemes are commonly used in controlling access to a communication bus. A scheme of this sort is described in U.S. Pat. No. 5,506,969, whose disclosure is incorporated herein by reference. A plurality of client applications operating on a computer system request services from a high-speed bus to transfer data from a source module to a destination module. A bus manager schedules transfer orders for the transfer requests based on a bus management policy. The bus manager implements a time-driven resource management policy, which aims to schedule all outstanding bus transfers in a shortest-deadline-first order, so that the transfers are executed in order of urgency.
Arbitration schemes are also used for routing packets and shaping traffic flow in packet-switched communication networks. For example, U.S. Pat. No. 5,689,508, whose disclosure is incorporated herein by reference, describes a reservation ring mechanism used for resolving conflicts among packet switch inputs contending for access to the same outputs. The reservation ring performs a sequence of step-and-compare operations in a top-to-bottom ring-like order during each arbitration cycle. The mechanism is consistent with the order required by self-clocked weighted fair queuing, with up to a maximum permissible number of contenders receiving access to any given output on each arbitration cycle.
U.S. Pat. Nos. 5,864,540 and 6,011,775, whose disclosures are incorporated herein by reference, describe a scalable integrated traffic shaper for use in a packet-switched network, and specifically for switching cells in an Asynchronous Transfer Mode (ATM) network. The shaper regulates multiple connections and prevents lost data by integrating link scheduling and traffic shaping to fairly arbitrate between incoming connections. It attempts to shape traffic at the edges of the network while equitably distributing bandwidth, even during periods of bursty traffic. For this purpose, cells coming into a switch are placed in per-connection queues. The cells are taken from the queues for processing based on round-robin scheduling. The scheduling is weighted in favor of high-bandwidth connections, so that each connection receives a quantity of cells that is proportionate to its bandwidth. For high-bandwidth queues, instead of taking one cell at a time, several cells from the input queue are processed simultaneously. The inventors note that the techniques they describe can also be used to schedule links in a network interior, so as to reduce packet delay jitter and downstream buffering requirements.
Other exemplary methods of fair arbitration and flow control in packet-switched networks are described in U.S. Pat. Nos. 5,926,459, 5,983,278 and 6,064,650, whose disclosures are likewise incorporated herein by reference.